package com.zhn;

/**
 * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
 *
 * 提醒一下，二叉搜索树满足下列约束条件：
 *
 * 节点的左子树仅包含键 小于 节点键的节点。
 * 节点的右子树仅包含键 大于 节点键的节点。
 * 左右子树也必须是二叉搜索树。
 *
 * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
 * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
 */

//相当于二叉搜索树中序遍历从右向左反方向遍历，再对节点数据做累加就可以
public class ConvertBST {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        //递归终止条件
        if(root == null)
            return null;
        //先右再左
        convertBST(root.right);
        root.val += sum;
        sum = root.val;
        convertBST(root.left);
        //更改的还是原先的节点，知识更新了节点数据变为累加
        return root;
    }
}
